package 链表;

/* https://leetcode-cn.com/problems/linked-list-cycle/ */
/* !!! 经典面试题 */

public class _141_环形链表 {

    class ListNode {
        // value
        int val;
        // next
        ListNode next;
        // 含参的构造函数
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public boolean hasCycle(ListNode head) {
        // 如果这个链表是空的，或者这个链表只有一个node，那么返回false
        if (head == null || head.next == null){
            return false;
        }else{
            // 解题核心：快慢指针。定义slow，等于head，定义fast等于head.next
            ListNode slow = head;
            ListNode fast = head.next;
            // 当fast或者fast.next不等于null，那么这个链表就还有元素
            while (fast != null && fast.next!= null){
                if (slow == fast){
                    return true;
                }
                // 让slow等于slow的next，相当于向前走一步，fast相当于向前走两步，这就是快慢指针
                slow = slow.next;
                fast = fast.next.next;

            }
        }
        return false;
    }
}
